package lc;

import java.util.*;
import org.junit.*;

public class Ex394 {
    class Solution1 {
        public String decodeString(String s) {
            Stack<Integer> nums = new Stack<>();
            Stack<String> alphas = new Stack<>();
            char[] cs = s.toCharArray();
            int len = cs.length, last = 0, k;
            char c;
            String t;
            String tmp, res;
            for (int i = 0; i < len; i++) {
                c = cs[i];
                if (isDigit(c)) {
                    int j = i;
                    while (j < len && isDigit(cs[j])) {
                        last = last * 10 + cs[j++] - '0';
                    }
                    nums.push(last);
                    last = 0;
                    i = j - 1;
                } else if (isAlpha(c)) {
                    int j = i;
                    tmp = "";
                    while (j < len && isAlpha(cs[j])) {
                        tmp += cs[j++];
                    }
                    alphas.push(tmp);
                    i = j - 1;
                } else {
                    if (c == '[') {
                        alphas.push(c + "");
                    } else {
                        tmp = "";
                        while (!alphas.isEmpty() && !(t = alphas.pop()).equals("[")) {
                            tmp = t + tmp;
                        }
                        k = nums.isEmpty() ? 1 : nums.pop();
                        res = "";
                        for (int j = 0; j < k; j++) {
                            res += tmp;
                        }
                        alphas.push(res);
                    }
                }
            }
            res = "";
            while (!alphas.isEmpty()) {
                res = alphas.pop() + res;
            }
            return res;
        }

        public boolean isDigit(char c) {
            return c >= '0' && c <= '9';
        }

        public boolean isAlpha(char c) {
            return c >= 'a' && c <= 'z' || c >= 'A' && c <= 'Z';
        }
    }

    @Test
    public void test() {
        Solution s = new Solution();
        // System.out.println(s.decodeString("3[a]2[bc]"));  
        System.out.println(s.decodeString("3[a2[c]]"));      
    }

    class Solution2 {
        public String decodeString(String s) {
            char[] cs = s.toCharArray();
            int len = cs.length, tmp, j, k;
            Stack<Integer> nums = new Stack<>();
            Stack<String> cals = new Stack<>();
            char c;
            String t;
            for (int i = 0; i < len; i++) {
                c = cs[i];
                if (isDigit(c)) {
                    tmp = 0;
                    j = i;
                    while (isDigit(cs[j])) {
                        tmp = tmp * 10 + cs[j] - '0';
                        j++;
                    }
                    nums.push(tmp);
                    i = j - 1;
                } else {
                    if (isAlpha(c) || c == '[') {
                        cals.push(c + "");
                    } else {
                        StringBuilder cur = new StringBuilder();
                        while (!("[".equals(t = cals.peek()))) {
                            cur.insert(0, t);
                            cals.pop();
                        }
                        k = nums.pop();
                        String str = cur.toString();
                        StringBuilder sb = new StringBuilder();

                        for (int l = 0; l < k; l++) {
                            sb.append(str);
                        }
                        cals.pop();
                        cals.push(sb.toString());
                    }
                }

            }
            StringBuilder sb = new StringBuilder();
            while (!cals.isEmpty()) {
                sb.insert(0, cals.pop());
            }
            return sb.toString();
        }

        public boolean isDigit(char c) {
            return c >= '0' && c <= '9';
        }

        public boolean isAlpha(char c) {
            return c >= 'a' && c <= 'z' || c >= 'A' && c <= 'Z';
        }
    }


    class Solution {
        public String decodeString(String s) {
            Stack<Integer> nums = new Stack<>();
            Stack<String> strs = new Stack<>();
            char[] cs = s.toCharArray();
            int n = cs.length;
            for (int i = 0; i < n; i++) {
                char c = cs[i];
                if (isDigit(c)) {
                    int res = 0, j = i;
                    while (j < n && isDigit(cs[j])) {
                        res = res * 10 + cs[j] - '0';
                        j++;
                    }
                    i = j - 1;
                    nums.push(res);
                } else if (c == '[') {
                    strs.push("[");
                } else if (c == ']') {
                    //出栈一个数字
                    int num = nums.pop();
                    StringBuilder sb = new StringBuilder();
                    while (!"[".equals(strs.peek())) {
                        sb.insert(0, strs.pop());
                    }
                    String cur = sb.toString();
                    sb = new StringBuilder();
    
                    //将[出栈
                    strs.pop();
                    for (int j = 0; j < num; j++){
                        sb.append(cur);
                    }
                    strs.push(sb.toString());
                } else {
                    //是普通的字符，将这一片字符串入栈
                    StringBuilder sb = new StringBuilder();
                    int j = i;
                    while (isAlpha(cs[j])) {
                        sb.append(cs[j]);
                        j++;
                    }
                    strs.push(sb.toString());
                    i = j - 1;
                }
            }
    
            while (!nums.isEmpty()) {
                //出栈一个数字
                int num = nums.pop();
                StringBuilder sb = new StringBuilder();
                while (!"[".equals(strs.peek())) {
                    sb.insert(0, strs.pop());
                }
                String cur = sb.toString();
                sb = new StringBuilder();
    
                //将[出栈
                strs.pop();
                for (int j = 0; j < num; j++){
                    sb.append(cur);
                }
                strs.push(sb.toString());
            }
    
            StringBuilder sb = new StringBuilder();
            while (!strs.isEmpty()) {
                sb.insert(0, strs.pop());
            }
            return sb.toString();
        }
    
        private boolean isDigit(char c) {
            return c >= '0' &&  c <= '9';
        }
    
        private boolean isAlpha(char c) {
            return c != '[' && c != ']' && !isDigit(c);
        }
    }

    @Test
    public void test2() {
        Solution s = new Solution();
        System.out.println(s.decodeString("3[a]2[bc]"));        
    }
}
